#include <stdio.h>
#include <stdio.h>
#include <string.h>

const int MAX_STR_LEN=1000;

int getMaxLen(char *s1, int lenth1, char *s2, int length2,int *result)
{
    for(int i=0; i<lenth1; i++)
    {
        for(int j=0; j<length2; j++)
        {
            if(s1[i]==s2[j])
            {
                result[(i+1)*(length2+1)+j+1] = result[i*(length2+1)+j]+1;
            }
            else
            {
                int len1 = result[(i+1)*(length2+1)+j];
                int len2 = result[i*(length2+1)+j+1];

                result[(i+1)*(length2+1)+j+1] = len1>len2 ? len1 : len2;
            }
        }// end of for(int j)
    }// end of for(int i...)

    return result[(lenth1)*(length2+1)+length2];
}

void forNowCoder(char *s1, char *s2, int *result)
{
	 while( scanf("%s", s1) != EOF)
    {
    	
        for(int i=0; i<MAX_STR_LEN; i++)
            result[i*MAX_STR_LEN] = 0;

        for(int i=1; i<MAX_STR_LEN; i++)
            result[i] = 0;

        int len = strlen(s1);
        for(int i=0; i<len; i++)
        {
            s2[i] = s1[len-1-i];
        }

        int res = len-getMaxLen(s1, len, s2, len, result);
        printf("%d\n", res);
    }
    
    return;
}

void forTest(char *s1, char *s2, int *result)
{
	 for(int i=0; i<MAX_STR_LEN; i++)
     	result[i*MAX_STR_LEN] = 0;

     for(int i=1; i<MAX_STR_LEN; i++)
     	result[i] = 0;
	
	scanf("%s", s1);
    scanf("%s", s2);

   	printf("%max Len: %d\n", getMaxLen(s1, strlen(s1), s2, strlen(s2), result) );
}

void getMaxSubStr(char *s1, int len1, int len2, int maxLen)
{
	
}

int main()
{
    char *s1 = new char[MAX_STR_LEN+1];
    char *s2 = new char[MAX_STR_LEN+1];
    int *result = new int[(MAX_STR_LEN+1)*(MAX_STR_LEN+1)];
    
	forTest(s1, s2, result);
//	forNowCoder(s1, s2, result);
    return 0;
}